package com.algrithom.recursive;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 47. 全排列 II
 */
public class Solution3 {
    
    public static void main(String[] args){
//                int[] nums = new int[]{1,1,2};
        //        int[] nums = new int[]{3,3,0,3};
        int[] nums = new int[]{0,1,0,0,9};
        Solution3 solution3 = new Solution3();
        List<List<Integer>> result = solution3.permuteUnique(nums);
//        result.forEach(System.out::println);
        System.out.println("*****");
//        nums = new int[]{0,1,0,0,9};
//        List<List<Integer>> result = solution3.permuteUnique2(nums);
        result.forEach(System.out::println);
    }
    
    public List<List<Integer>> permuteUnique(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int[] visited = new int[nums.length];
        backtrack(0,res,nums,new ArrayList<>(),visited);
        return res;
        
    }
    
    private void backtrack(int index,List<List<Integer>> res,int[] nums,ArrayList<Integer> tmp,int[] visited){
        if (index == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (visited[i] == 1 || (i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0)) {
                continue;
            }
            tmp.add(nums[i]);
            visited[i] = 1;
            backtrack(index + 1,res,nums,tmp,visited);
            tmp.remove(tmp.size() - 1);
            visited[i] = 0;
        }
    }
    
    public List<List<Integer>> permuteUnique2(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        boolean[] visited = new boolean[n];
        Collections.sort(output);
        backtrack(n,output,res,0,visited);
        return res;
    }
    
    public void backtrack(int n,List<Integer> output,List<List<Integer>> res,int first,boolean[] visited){
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<>(output));
        }
        for (int i = first; i < n; i++) {
            if (visited[i] || (i > 0 && output.get(i).equals(output.get(i - 1)) && !visited[i-1])) {
                continue;
            }
            visited[i] = true;
            // 动态维护数组
            Collections.swap(output,first,i);
            // 继续递归填下一个数
            backtrack(n,output,res,first + 1,visited);
            // 撤销操作
            Collections.swap(output,first,i);
            visited[i] = false;
        }
    }
}
